package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/minimum-additions-to-make-valid-string/'>构造有效字符串的最少插入数(Minimum Additions to Make Valid String)</a>
 * <p>给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。</p>
 * <p>如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：word = "b"
 *      输出：2
 *      解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
 *
 * 示例 2：
 *      输入：word = "aaa"
 *      输出：6
 *      解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
 *
 * 示例 3：
 *      输入：word = "abc"
 *      输出：0
 *      解释：word 已经是有效字符串，不需要进行修改。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= word.length <= 50</li>
 *     <li>word 仅由字母 "a"、"b" 和 "c" 组成。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/12 9:17
 */
public class LC2645MinimumAdditionsToMakeValidString_M {
    static class Solution {
        public int addMinimum(String word) {
            int n = word.length();
            int group = 1;
            for (int i = 1; i < n; i++) {
                // 正常一组是abc，后一个字符会大于前一个字符。如果后一个字符小于等于前一个字符，说明出现了新的一组
                if (word.charAt(i) <= word.charAt(i - 1)) {
                    ++group;
                }
            }
            return group * 3 - n;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.addMinimum("b"));
        System.out.println(solution.addMinimum("aaa"));
        System.out.println(solution.addMinimum("abc"));
        System.out.println(solution.addMinimum("aaaabb"));
    }
}
